package org.example.leetcode;

import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description: 求数的子集
 * @date: 2021/7/26 19:13
 */
public class LC78 {
    public static void main(String[] args) {
            LC78 lc=new LC78();
            int[] nums={1,2,3};
            System.out.println(lc.subsets(nums));
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if (nums.length==0 ||nums==null) return res;
        List<Integer> curList=new ArrayList<>();
        res.add(new ArrayList<>());//fixme 空也是子集
        int[] visible=new int[nums.length];
        backTrack(nums,0,res,curList,visible);
        return res;
    }
    //fixme https://www.bilibili.com/video/BV1Ji4y1j7rt?from=search&seid=9351057199928918015
    private void backTrack(int[] nums,int start,List<List<Integer>> res,List<Integer> curList,int[] v){
        if (start>=nums.length)  return;
        for (int i = start; i <nums.length ; i++) {
            if (v[i]==1) continue;
            v[i]=1;
            curList.add(nums[i]);
            res.add(new ArrayList<>(curList)); //fixme 全排列
            backTrack(nums,i+1,res,curList,v);//fixme 是 i+1 ，不是 start +1
            curList.remove(curList.size()-1);
            v[i]=0;
        }
    }
}
